package euler.helper;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;

public class NaturalHelper {

	private final PrimeHelper primeHelper;
    private static long[] factoriales = new long[]{1,1};
    private static long[] fibonaccis = new long[]{0,1};

    private static final int limiteFactoriales = 20;

    public NaturalHelper(PrimeHelper primeHelper) {
    	this.primeHelper =  primeHelper;
	}

    public static long factorial(int n) {

        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        } else if (n > limiteFactoriales)  {
            throw new IllegalArgumentException("Numero demasiado grande para factorial");
        }

        ensureCapacityFactoriales(n);

        return factoriales[n];
    }

    private static void ensureCapacityFactoriales(int n) {

        if (factoriales.length <= n) {
            long[] aux = factoriales;

            int m = (int)Math.pow(2, (int)(Math.log(n)/Math.log(2)) + 1);
            m = Math.max(m, limiteFactoriales+1);
            factoriales = new long[m];

            System.arraycopy(aux, 0, factoriales, 0, aux.length);

            for (int i= aux.length; i<factoriales.length; i++) {
                factoriales[i] = factoriales[i - 1] * i;
            }
        }
    }

    public static long fibonacci(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        }

        ensureCapacityFibonaccis(n);

        return fibonaccis[n];
    }

    private static void ensureCapacityFibonaccis(int n) {

        if (fibonaccis.length <= n) {
            long[] aux = fibonaccis;

            int m = (int)Math.pow(2, (int)(Math.log(n)/Math.log(2)) + 1);
            fibonaccis = new long[m];

            System.arraycopy(aux, 0, fibonaccis, 0, aux.length);

            for (int i= aux.length; i<fibonaccis.length; i++) {
                fibonaccis[i] = fibonaccis[i - 1] + fibonaccis[i - 2];
            }
        }
    }

    public static int cantidadDigitos(long n, int base) {
        int suma = 0;

        while (n > 0) {
            n/=base;
            suma++;
        }

        return suma;
    }

    public static boolean isPalindromo(long n, int base) {

        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        } else if (n < base) {
            return true;
        } else if (n % base == 0) {
            return false;
        }

        int digitos = cantidadDigitos(n,base);

        for (int i = 0; i <= digitos/2; i++) {
            if (digito(n,i,base) != digito(n,digitos-i-1,base)) {
                return false;
            }
        }

        return true;
    }


    public static int digito(long n, int d, int base) {

        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        } else if ((n < base) && (d == 0)) {
            return (int)n;
        } else if (n < base) {
            return 0;
        }

        int r = 0;

        for (int i = 0; i <= d; i++) {
            if (n == 0) {
                r = 0;
                break;
            }
            r = (int)n % base;
            n/=base;
        }

        return r;
    }

    public static boolean isPalindromo(long n) {
        return isPalindromo(n,10);
    }


    // Pentagonal      P(n)=n(3n−1)/2        1, 5, 12, 22, 35, ...
    public static boolean isPentagonal(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        }

        double raiz = Math.sqrt(1 + 24*n);

        if ((long)raiz == raiz) {
            double antiP = (1 + raiz) / 6;

            return ((long)antiP == antiP);
        }

        return false;
    }

    // Hexagonal       H(n)=n(2n−1)      1, 6, 15, 28, 45, ...
    public static boolean isHexagonal(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        }

        long m = 1 + 8*n;

        if (isSquare(m)) {
        	double raiz = Math.sqrt(m);
            double antiH = (1 + raiz) / 4;

            return ((long)antiH == antiH);
        }

        return false;
    }

    //  Triangle        T(n)=n(n+1)/2         1, 3, 6, 10, 15, ...
    public static boolean isTriangle(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        }

        long d = 2*n;
        long i = (long)Math.sqrt(d);

        return i * (i+1) == d;
    }

    public static long reverso(long n, int base) {

        if (n < 0 || base < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        } else if (n < base) {
            return (int) n;
        }

        int digitos = cantidadDigitos(n,base);
        long r = 0;
        long d = 1;

        for (int i = 1; i <= digitos; i++) {
            r+=(digito(n, digitos-i, base) * d);
            d*=base;
        }

        return r;
    }

    public static boolean isPalindromo(BigInteger n) {
        return isPalindromo(n,10);
    }

    public static boolean isPalindromo(BigInteger n, int base) {
        if (n.signum() < 0 || base < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        } else if (n.compareTo(BigInteger.valueOf(base)) < 0) {
            return true;
        } else if (n.remainder(BigInteger.valueOf(base)).equals(BigInteger.ZERO)) {
            return false;
        }

        int digitos = cantidadDigitos(n,base);

        for (int i = 0; i <= digitos/2; i++) {
            if (digito(n,i,base) != digito(n,digitos-i-1,base)) {
                return false;
            }
        }

        return true;
    }

    public static BigInteger reverso(BigInteger n, int base) {

        if (n.signum() < 0 || base < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        } else if (base == 10) {
            return new BigInteger(reverseString(n.toString()));
        }

        BigInteger iBase = BigInteger.valueOf(base);
        if (n.compareTo(iBase) < 0) {
            return n;
        }

        int digitos = cantidadDigitos(n,base);
        BigInteger r = BigInteger.ZERO;
        BigInteger d = BigInteger.ONE;

        for (int i = 1; i <= digitos; i++) {
            r = r.add(d.multiply(BigInteger.valueOf(digito(n, digitos-i, base))));
            d = d.multiply(iBase) ;
        }

        return r;
    }

    private static String reverseString(String s) {

    	if (s == null) {
    		return null;
    	} else if (s.length() == 1) {
    		return s;
    	}

        char[] in = s.toCharArray();
        char[] out = new char[in.length];

        for (int i = 0; i < out.length; i++) {
            out[i] = in[out.length - i - 1];
        }

        return new String(out);
    }

    private static int digito(BigInteger n, int d, int base) {
        if (n.signum() < 0 || base < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        }

        BigInteger iBase = BigInteger.valueOf(base);
        if (n.compareTo(iBase) < 0) {
            return n.intValue();
        }

        int r = 0;

        for (int i = 0; i <= d; i++) {
            if (n.signum() == 0) {
                r = 0;
                break;
            }
            r = n.remainder(iBase).intValue();
            n = n.divide(iBase);
        }

        return r;
    }

    public static int cantidadDigitos(BigInteger n, int base) {
        int suma = 0;
        BigInteger bigBase = BigInteger.valueOf(base);

        while (n.signum() != 0) {
            n = n.divide(bigBase);
            suma++;
        }

        return suma;
    }

    public static int sumaDigital(BigInteger n) {
        int suma = 0;

        while (n.signum() != 0) {
            suma+=n.remainder(BigInteger.TEN).intValue();
            n = n.divide(BigInteger.TEN);
        }

        return suma;
    }

    /**
     *   Euler's Totient function, φ(n) [sometimes called the phi function],
     *   is used to determine the number of numbers less than n which are
     *   relatively prime to n.
     *   The totient function is a multiplicative function,
     *   meaning that if two numbers m and n are relatively prime
     *   (to each other), then φ(mn) = φ(m)φ(n)
     *   if p is prime then
     *   φ(p^k) = (p − 1)*p^(k − 1)
     */
    public int phi(int n) {

        if (n < 1) {
            throw new IllegalArgumentException("Parametro menor que 1");
        } else if (n == 1) {
            return 1;
        } else if (this.primeHelper.isPrime(n)) {
            return n - 1;
        }

        int phi = 1;
        for (Pair<Long, Integer> factor: this.primeHelper.factorizar(n)) {
            phi*=((int)Math.pow(factor.left, factor.right - 1) * (factor.left - 1));
        }

        return phi;
    }

    public byte[][] permutaciones(String s) {

        int length = (s == null) ? 0 : s.length();

        if (length == 0) {
            byte[][] baa = new byte[0][0];
            return baa;
        } else if (length == 1) {
            byte[][] baa = new byte[1][1];
            baa[0][0]=(byte)(s.charAt(0) - '0');
            return baa;
        }

        byte[][] baa = new byte[(int)factorial(length)][length];
        int k = 0;
        for (int i = 0; i < length; i++) {
            byte b = (byte)(s.charAt(i) - '0');

            byte[][] baa2 = permutaciones(s.substring(0,i) + s.substring(i+1));

            for (int j = 0; j < baa2.length; j++) {
                byte[] ba = new byte[baa2[j].length + 1];
                ba[0] = b;
                System.arraycopy(baa2[j], 0, ba, 1, baa2[j].length);
                baa[k++] = ba;
            }
        }

        return baa;
    }

    public static int[] digitos(int n, int base, boolean sort) {

        int digitos = cantidadDigitos(n, base);
        int[] r = new int[digitos];

        for (int i = 0; i < r.length; i++) {
            r[i] = n%base;
            n/=base;
        }

        if (sort) {
			Arrays.sort(r);
		} else {
			Utils.reverse(r);
		}

        return r;
    }

    public static BigDecimal squareRoot(BigInteger n) {
        BigDecimal myNumber = new BigDecimal(n);
        BigDecimal g = BigDecimal.ONE;
        BigDecimal my2 = BigDecimal.valueOf(2);
        BigDecimal epsilon = new BigDecimal("0.1");

        BigDecimal nByg = myNumber.divide(g, 9, BigDecimal.ROUND_FLOOR);

        BigDecimal nBygPlusg = nByg.add(g);

        BigDecimal nBygPlusgHalf =  nBygPlusg.divide(my2, 9, BigDecimal.ROUND_FLOOR);

        BigDecimal saveg = nBygPlusgHalf;
        int firsttime = 99;

        do {
            g = nBygPlusgHalf;
            nByg = myNumber.divide(g, 9, BigDecimal.ROUND_FLOOR);
            nBygPlusg = nByg.add(g);
            nBygPlusgHalf =  nBygPlusg.divide(my2, 9, BigDecimal.ROUND_FLOOR);
            BigDecimal  savegdiff  = saveg.subtract(nBygPlusgHalf);

            if (savegdiff.compareTo(epsilon) == -1 ) {
                firsttime = 0;
            } else {
                saveg = nBygPlusgHalf;
            }

        } while (firsttime > 1);

        return saveg;
    }

    public static BigInteger bigFactorial(int r) {
        BigInteger fac = BigInteger.ONE;
        for (int i = 1; i <= r; i++) {
            fac=fac.multiply(BigInteger.valueOf(i));
        }
        return fac;
    }

    public static boolean isSquare(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        }

        long m = n % 16;

        if (m != 0 && m != 1 && m != 4 && m != 9) {
        	return false;
        } else {
        	long raiz = (long)Math.sqrt(n);

            return (raiz*raiz == n);
        }
    }

    public static boolean isHeptagonal(long n) {
        if (n < 0) {
            throw new IllegalArgumentException("Parametro menor que 0");
        }

        long m = 9 + 40*n;

        if (isSquare(m)) {
        	double raiz = Math.sqrt(m);
            double antiH = (3 + raiz) / 10;

            return ((long)antiH == antiH);
        }

        return false;
    }

	public static long toNumber(int[] digitos, int base) {
		long n = 0;

		if (digitos != null) {
			for (int i = 0; i < digitos.length; i++) {
				n = n + digitos[i];

				if (i < digitos.length -1) {
					n= n * base;
				}
			}
		}

		return n;
	}
}
